Basic power method convergence

Let $\gamma = \frac{\sigma_1 - \sigma_2}{\sigma_1}$ be parameter capturing the “gap” between the first and second largest singular values. If Power method is initialized with a random Gaussian vector, then with high probability, after $T=O(\frac{\log d/\epsilon}{\gamma})$ steps, we have either:

The method won’t converge if $\gamma$ is very small. Consider extreme case when $\gamma = 0$.

#incomplete